package mess;

import com.sun.org.apache.xml.internal.utils.IntStack;

import java.util.Arrays;
import java.util.Random;

public class
A_quickSort {
    public static void main(String[] args) {
//        int[] nums = new int[100000];
//        Random r = new Random();
//        for (int i = 0; i < nums.length; i++)
//            nums[i] = r.nextInt(1000000000);
//        quickSort(nums, 0, nums.length - 1);
//        System.out.println(Arrays.toString(nums));
        int[] arr = new int[50000];
        for (int i = 50000, j = 0; i > 0; i--, j++) {
            arr[j] = i;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    private static void quickSort(int[] nums, int i, int j){
        if (i >= j)
            return;
        int start = i;
        int end = j;
        int baseNum = nums[i];
        while (start != end){
            while (true){
                if (start >= end || nums[end] < baseNum)
                    break;
                end--;
            }
            while (true){
                if (start >= end || nums[start] > baseNum) {
                    break;
                }
                start++;
            }
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
        }
        nums[i] = nums[start];
        nums[start] = baseNum;
        quickSort(nums, i, start - 1);
        quickSort(nums, start + 1, j);
    }
}
